package greedy_algorithm;

import java.util.ArrayList;
import java.util.List;


class point {
	double x;
	double y;
	point(double x,double y){
		this.x=x;
		this.y=y;
	}
	public String toString(){
		String str="("+this.x+","+this.y+")";
		return str;
	}
}
public class Nearest_neighbor_strategy {
	
	//该方法使用了贪心算法中最近邻的方法
	public static List<point> TSP(List<point> in,int start){
		List<point> out=new ArrayList<point>();
		double sum=0;
		if(in.size()==0) {
			return out;
		}
		if(in.size()==1) {
			out.add(in.get(in.size()-1));
			return out;
		}
		out.add(in.get(start));
		in.remove(start);
		while(in.size()!=0) {
			int mid_subscript=-1;
			double mid_distance=Integer.MAX_VALUE;
			for(int i=0;i<in.size();i++) {
				if(mid_distance>dist(out.get(out.size()-1),in.get(i))) {
					mid_distance=dist(out.get(out.size()-1),in.get(i));
					mid_subscript=i;
				}
			}
			sum=sum+mid_distance;
			
			out.add(in.get(mid_subscript));
			in.remove(mid_subscript);
		}
		sum=sum+dist(out.get(0),out.get(out.size()-1));
		System.out.println(sum);
		return out;
	}
	
	static double dist(point p1,point p2) {
		return Math.sqrt(Math.pow((p2.x-p1.x), 2)+Math.pow((p2.y-p1.y), 2));
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		point a1=new point(569,738);
		point a2=new point(231,433);
		point a3=new point(345,987);
		point a4=new point(564,897);
		point a5=new point(134,897);
		point a6=new point(908,234);
		point a7=new point(687,343);
		point a8=new point(569,246);
		point a9=new point(679,146);
		point a0=new point(681,874);
		List<point> in=new ArrayList<point>();
		in.add(a1);in.add(a0);in.add(a9);in.add(a8);in.add(a7);in.add(a6);in.add(a5);in.add(a4);in.add(a3);in.add(a2);
		in=TSP(in,0);
		for(int i=0;i<in.size();i++) {
			System.out.print("("+in.get(i).x+","+in.get(i).y+")");
		}
	}

}
